题目

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example: For num = 5
you should return [0,1,1,2,1,2]

Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

这个题目大意是给定一个非负数num, 然后让我们计算0~num之间每一个数字的二进制表示中1的个数并以数组的形式返回。其中要求时间复杂度和空间复杂度均为O(n)。

失败的解决案例

看到这个题目时，我第一时间想到的解决方案是:

  1. 第一步毋庸置疑，一定是对0～num进行遍历，至于是for还是while循环都可以。
  2. 循环体中的操作
    • 将数字转换为二进制字符串 num.toString(2)
    • 对二进制字符串进行遍历，这里使用通用的for...in还是Object.keys()都可行。不过这里我们采用的是先用空串分割转换为数组之后，就可以直接使用数组的forEach方法进行遍历操作了
    • 使用临时变量在循环体中对当前数字中1的个数进行统计，然后push进数组即可。

Code

function countBits (num) {
    if (!num && num !== 0) return
    let result = []
    while (num >= 0){
        let count = 0
        num.toString(2).split('').forEach(a => a === '1' && count++)
        result.unshift(count)
        num--
    }
    return result
}

不知大家有没有发现，该solution的时间复杂度因为两层的嵌套循环使得时间复杂度已经超越O(n^2)了, 由于里层循环的次数与n含有函数关系，暂且把它当作是O(n^2)的复杂度吧 ! 结果可想而知，在OJ过程中没有被Accept……

思考 : 现在问题来了，如果要把时间复杂度控制在O(n)上，就意味着在外层必须要的循环里，要保证内层操作的时间复杂度为O(1)，也就意味着内层不能用循环来处理。

百思不得解后，很没出息的翻开了Hint提示，如下：

  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. Or does the odd/even status of the number help you in calculating the number of 1s?
  1. 你应该利用已经计算出的部分结果
  2. [2-3], [4-7], [8-15] 以这个区间的形式对数字进行划分，并且尝试对前边已经利用过的数据进行重新分组
  3. 或者也可以对数字的奇偶性切入判断

官方建议解法一

分析:

第二条中讲到对数字进行分组，我们先通过js程序将0～32之间的数字的二进制值打印一下，分析一下结构规律：

0:      0000    0001   
2:      0010    0011
4:      0100    0101     0110     0111
8:      1000    1001     1010     1011    1100    1101    1110    1111
16:    10000...

将数据按照2的次幂分组后，发现每逢二的次幂，该行的数据全部跟前边若干行的数据有关，具体如下：

总结上图规律：

  1. 每行开头的值都是2的次幂，这意味着发生了总位数的增加。因为固定二进制位数能表示的范围是0～2^n－1。在最高位加了1后，后半部分(当前行)值的增长本质上是对前半部分的复制，也就是说抛开增长的最高位，后边的几位数盒前半部分值是完全相同的。
  2. 由此推断出当前行每一个数字中1的位数都比前半部分所对应的数字多1个(最高位)
  3. 我们只要抓准当前行的开始值，然后对前几行的数据从0开始记录，直到最后一个数字，依次加一即可完成对当前数字中1个数的推算。

Code：

function countBits (num) {
    let result = [0];
    let pow = 1
    for(let i = 1, t = 0; i <= num; i++, t++) {
        if(i == pow) { // 抓取是否是行首值
            pow *= 2
            t = 0 // 对前半部分的纪录游标置零
        }
        result[i] = result[t] + 1 // 对当前遍历中的每一个元素+1
    }
    return result
}

直接看代码可能还是有难度的，通过分析之后，发现还是非常通读易懂的。

官方建议解法二

本解法的途径则是根据数字的奇偶性来作为切入点

分析

  1. 妇孺皆知，偶数后必然是奇数，也就是最后一个二进制位是1，前几位都一样。
  2. 对一个偶数除2取整，则可以计算出与之对应1个数相同的数。这样不好理解也可以利用>>位运算的方式增强理解。对一个偶数(最低位为0)向右移动一位(除二)可以推理出与之相同1个数的数；对于奇数而言，其1个数的统计只比前一个大1。
  3. 列计算式： re[i] = re[i / 2] + i % 2
    Code: 
    public int[] countBits(int num) {
            int[] f = new int[num + 1];
            for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
            return f;
        }

小记：

  1. 这里的运算方式中，取余时采用了’&’，位运算的乘法，这也是取出最低位数字(余数)的一种较为简便的方
    式。
  2. 由于Javascript中没有取整运算，因此如果用Javascript作为语言的话，如果不用位运算，就得要用以下几种函数了：
    • Math.floor(num) 向下取整
    • Math.ceil(num) 向上取整
    • parseInt(num) 向下取整
    • Math.round(num) 四舍五入
    • num.toFixed(x) 选择保留小数位数，取值遵循四舍五入

总结：

  • 寻找规律
  • 利用双游标进行判断对比，第一个游标完成对前半部分的遍历，同时平行生成后半部分数据，从而达到O(n)的时间复杂度
  • Coding…

内容目录

  1. 题目
  2. 失败的解决案例
    1. Code
  3. 官方建议解法一
    1. 分析:
    2. Code：
  4. 官方建议解法二
    1. 分析
  5. 总结：
donation